/**
 * //English description is not available for the problem. Please switch to
 * //Chinese.
 * // Related Topics 栈 数组 模拟 👍 385 👎 0
 */

package com.xixi.dataStructure.stack;

import java.util.Stack;

public class ID_Offer_31_ZhanDeYaRuDanChuXuLieLcof {
    public static void main(String[] args) {
        Solution solution = new ID_Offer_31_ZhanDeYaRuDanChuXuLieLcof().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean validateStackSequences(int[] pushed, int[] popped) {

            if (popped.length == 0) return true;
            Stack<Integer> stack = new Stack<>();

            //empty stack init using pushed[0]
            int pu = 0;
            int po = 0;

            //pop must be invoked after push
            while (pu < pushed.length) {
                if (stack.isEmpty()) {
                    stack.push(pushed[pu]);
                    pu++;
                }

                //every time judge next move
                int top = stack.peek();
                if (top == popped[po]) {
                    stack.pop();
                    po++;
                } else {
                    stack.push(pushed[pu]);
                    pu++;
                }
            }
            //then, every thing pushed done
            while (po < popped.length) {
                int top = stack.pop();
                if (top != popped[po]) return false;
                po++;
            }


            return true;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}